package com.mystudy.leetcode.problem.link.p_142;

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.Test;

import java.util.HashSet;

/**
 * @program: infoalgorithm
 * @description: 中等题目:环形链表2
 * @author: zhouzhilong
 * @create: 2019-07-08 10:54
 **/
public class Solution {

    @Test
    public void test(){
        ListNode listNode = ListNodeUtils.geneCircleLinkList(new int[]{1, 3, 4, 7, 9}, 1);
        ListNode listNode1 = detectCycle(listNode);
        System.out.println(listNode1.val);
    }


    /**
     * HashSet法
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> visited = new HashSet<>();

        ListNode cur = head;
        while (cur != null) {
            if (visited.contains(cur)) {
                return cur;
            }
            visited.add(cur);
            cur = cur.next;
        }

        return null;
    }
}
